// https://leetcode-cn.com/problems/coin-change/
// 322. Coin Change
// You are given an integer array coins representing coins of different denominations and an
// integer amount representing a total amount of money
//
// Return the fewest number of coins that you need to make up that amount. If that amount of
// money cannot be made up by any combination of the coins, return -1.
//
// You may assume that you have an infinite number of each kind of coin.
function coinChange(coins: number[], amount: number): number {
    const max = amount + 1;
    const dp = new Array(max).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (i - coins[j] >= 0) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    return dp[amount] < Infinity ? dp[amount] : -1;
}

const result = coinChange([2, 3], 1);
console.log(result);
